#include <Trie.hpp>
#include <stack>

template <typename T>
GTrie<T>::GTrie() : qtyChildren(0) {
	children = std::vector<GTrie *>(52, (GTrie*)0);
}

template <typename T>
GTrie<T>::~GTrie() {
	for (int i = 0; i < 52; i++)
		if (children[i])
			delete children[i];
}

template <typename T>
void GTrie<T>::insert(std::string word, T value) {
	int sz = word.length();
	GTrie<T> * curnode = this;

	for (int i = 0; i < sz; i++) {
		int pos = Trie::convertToIndice(word[i]);
		if (!curnode->children[pos]) {
			curnode->children[pos] = new GTrie();
			curnode->qtyChildren++;
		}
		curnode = curnode->children[pos];
	}
	curnode->values.push_back(value);
}

template <typename T>
std::vector<T> GTrie<T>::retrieve(std::string word) {
	int sz = word.length();
	GTrie<T> * curnode = this;

	for (int i = 0; i < sz; i++) {
		int pos = Trie::convertToIndice(word[i]);
		if (!curnode->children[pos])
			return std::vector<int>();
		curnode = curnode->children[pos];
	}
	return curnode->values;
}

template <typename T>
void GTrie<T>::remove(std::string word) {

	int sz = word.length();
	GTrie<T> * curnode = this;

	std::stack<std::pair<int, GTrie<T> *> > stack;

	int pos;
	for (int i = 0; i < sz; i++) {
		pos = Trie::convertToIndice(word[i]);
		if (!curnode->children[pos])
			return;
		stack.push(std::pair<int, GTrie*>(pos, curnode));
		curnode = curnode->children[pos];
	}

	curnode->values.clear();

	if (!curnode->qtyChildren) {
		delete curnode;
		while (!stack.empty()) {
			std::pair<int, GTrie*> top = stack.top();
			stack.pop();
			top.second->children[top.first] = 0;
			if (--top.second->qtyChildren || top.second->values.size())
				break;
			if (!stack.empty())
				delete top.second;
		}
	}

}


